package com.lsa.skienna.challenge.chap9.the110902_PlayingWithWheels;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main implements Runnable{
    private static final int WHEEL_NUMBER = 4;
    private static final int CONFIGURATION_NUMBER = pow(10, WHEEL_NUMBER);
    
    public static void main(String[] args) throws Exception {
        new Main().run();
    }
    
    @Override
    public void run() {
        process(System.in, System.out);
    }
    
    static void process(InputStream in, PrintStream out) {
        TaskReader taskReader = new TaskReader(in);
        try {
            Task task = null;
            while((task = taskReader.nextTask()) != null){
                // out.println(solveAStar(task));
                out.println(solveBruteForce(task));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    
    /**
     * Solves with BFS
     * @param task
     * @return minimum number of button press
     */
    static int solveBruteForce(Task task) {
        Queue<Configuration> queue = new LinkedList<Configuration>();
        
        int[] parentRelation = new int[CONFIGURATION_NUMBER];
        Arrays.fill(parentRelation, -1);
        boolean[] discovered = new boolean[CONFIGURATION_NUMBER];
        
        queue.add(task.startConf);
        discovered[task.startConf.number] = true;
        
        if (!task.forbiddenConfs.contains(task.startConf)) {
            while(!queue.isEmpty()) {
                Configuration v = queue.poll();
                if (task.targetConf.number == v.number) {
                    return calcPathEdgeCount(parentRelation, v.number);
                }
                
                List<Configuration> edgeEndpoints = calcEdgeEndpoints(v, task);
                for (int i = 0; i < edgeEndpoints.size(); i++) {
                    Configuration u = edgeEndpoints.get(i);
                    if (!discovered[u.number] && !task.forbiddenConfs.contains(u)) {
                        discovered[u.number] = true;
                        parentRelation[u.number] = v.number;
                        queue.add(u);
                    }
                }
            }
        }
        
        
        return -1;
    }
    
    static void enqueue(Configuration conf,
            PriorityQueue<Configuration> frontier,
            Map<Integer, Configuration> confNumber2Conf) {
        frontier.add(conf);
        confNumber2Conf.put(conf.number, conf);
    }
    
    static Configuration dequeue(PriorityQueue<Configuration> frontier,
            Map<Integer, Configuration> confNumber2Conf) {
        final Configuration head = frontier.poll();
        confNumber2Conf.remove(head.number);
        return head;
    }
    
    static int solveAStar(Task task) {
        PriorityQueue<Configuration> frontier = new PriorityQueue<Configuration>(10, new Comparator<Configuration>() {
            @Override
            public int compare(Configuration o1, Configuration o2) {
                return o1.fscore() - o2.fscore();
            }
        });
        Map<Integer, Configuration> confNumber2Conf = new HashMap<Integer, Configuration>();
        
        int[] parentRelation = new int[CONFIGURATION_NUMBER];
        Arrays.fill(parentRelation, -1);
        Set<Configuration> closed = new HashSet<Configuration>();
        
        task.startConf.gscore = 0;
        task.startConf.updateHScore(task.targetConf);
        
        enqueue(task.startConf, frontier, confNumber2Conf);
        closed.add(task.startConf);
        
        if (!task.forbiddenConfs.contains(task.startConf)) {
            while(!frontier.isEmpty()) {
                Configuration x = dequeue(frontier, confNumber2Conf);
                if (x.equals(task.targetConf)){
                    return calcPathEdgeCount(parentRelation, x.number);
                }
                
                closed.add(x);
                
                List<Configuration> edgeEndpoints = calcEdgeEndpoints(x, task);
                for (int i = 0; i < edgeEndpoints.size(); i++) {
                    Configuration y = edgeEndpoints.get(i);
                    if (!closed.contains(y) && !task.forbiddenConfs.contains(y)) {
                        int neighbourGScore = x.gscore + 1;
                        boolean isNeighborBetter = false;
                        if (!confNumber2Conf.containsKey(y.number)) {
                            isNeighborBetter = true;
                        }
                        else {
                            y = confNumber2Conf.get(y.number);
                            if (neighbourGScore < y.gscore) {
                                frontier.remove(y);
                                isNeighborBetter = true;
                            }
                        }
                        
                        if (isNeighborBetter) {
                            parentRelation[y.number] = x.number;
                            y.gscore = neighbourGScore;
                            y.updateHScore(task.targetConf);
                            frontier.add(y);
                            enqueue(y, frontier, confNumber2Conf);
                        }
                    }
                }
            }
        }
        
        return -1;
    }
    
    public static int calcPathEdgeCount(int[] parentRelation, int number) {
        int pathEdgeCount = 0;
        final boolean isPrintSolution = false;
        while(parentRelation[number] != -1) {
            pathEdgeCount++;
            if (isPrintSolution) System.err.println("*"+stringify(number));
            number = parentRelation[number];
        }
        if (isPrintSolution) System.err.println("*"+stringify(number));
        if (isPrintSolution) System.err.println("***");
        
        return pathEdgeCount;
    }
    
    static String stringify(int number){
//        final char[] chars = (""+number).toCharArray();
//        return StringUtils.join(ArrayUtils.toObject(chars), ' ');
        return ""+number;
    }
    
    public static void outputInteger(PrintStream ps, int n) {
        String s = String.format("%04d", n);
        for (int i = 0; i < s.length(); i++) {
            ps.print(s.charAt(i));
            ps.print(' ');
        }
        ps.println();
    }
    
    static List<Configuration> calcEdgeEndpoints(Configuration conf, Task task){
        List<Configuration> edgeEndpoints = new ArrayList<Configuration>();
        
        for (int i = 0; i < WHEEL_NUMBER; i++) {
            for (boolean isLeft : new boolean[]{true, false}) {
                final Configuration newConf = conf.pressButton(i, isLeft);
                if (!task.forbiddenConfs.contains(newConf)) {
                    edgeEndpoints.add(newConf);
                }
            }
        }
        
        return edgeEndpoints;
    }
    
    static class TaskReader{
    	private Scanner scanner;
        private boolean isFirst;
        private int caseNumber;

        TaskReader(InputStream stream) {
            this.scanner = new Scanner(stream);
            this.isFirst = true;
        }
        
        Task nextTask() throws IOException {
            if (isFirst) {
                caseNumber = scanner.nextInt();
                isFirst = false;
            }
            
            Task task = null;
            
            if (caseNumber-- > 0) {
                task = new Task();
                task.startConf = readConfiguration();
                task.targetConf = readConfiguration();
                int noOfForbiddenConfs = scanner.nextInt();
                for (int i = 0; i < noOfForbiddenConfs; i++) {
                    task.forbiddenConfs.add(readConfiguration());
                }
            }
            
            return task;
        }
        
        Configuration readConfiguration() throws IOException{
            int[] numbers = new int[WHEEL_NUMBER];
            for (int i = 0; i < WHEEL_NUMBER; i++) {
                numbers[i] = scanner.nextInt();
            }
            return new Configuration(numbers);
        }
    }
    
    static class Task{
        Configuration startConf;
        Configuration targetConf;
        
        Set<Configuration> forbiddenConfs = new HashSet<Configuration>();
    }
    
    static class Configuration{
        final int number;
        int gscore;
        int hscore;

        Configuration(int[] numbers) {
            number = calcNumber(numbers);
        }
        
        int fscore() {
            return gscore + hscore;
        }
        
        void updateHScore(Configuration target) {
            hscore = manhattanDistance(target);
        }
        
        Configuration pressButton(int buttonNumber, boolean isLeftOrRight ) {
            int[] numbers = decompose();
            
            numbers[buttonNumber] += isLeftOrRight? 1 : -1;
            if (numbers[buttonNumber] == 10) {
                numbers[buttonNumber] = 0;
            }
            else if (numbers[buttonNumber] == -1) {
                numbers[buttonNumber] = 9;
            }
            
            return new Configuration(numbers);
        }

        int[] decompose() {
            int[] numbers = new int[WHEEL_NUMBER];
            
            int num = number;
            int i = WHEEL_NUMBER;
            while (num > 0)
            {
                int digit = num%10;
                numbers[--i] = digit;
                num /= 10;
            }
            return numbers;
        }
        
        int manhattanDistance(Configuration other) {
            int dist = 0;
            int[] numbers = decompose();
            int[] otherNumbers = other.decompose();
            for (int i = 0; i < WHEEL_NUMBER; i++) {
                dist += wheelDist(numbers[i], otherNumbers[i]);
            }
            
            return dist;
        }
        
        int wheelDist(int x, int y) {
            return Math.min(Math.abs(x - y), Math.min(x + 10 - y, y + 10 - x));
        }
        
        int calcNumber(int[] numbers) {
            int number = 0;
            for (int i = 0; i < WHEEL_NUMBER; i++) {
                number += pow(10, WHEEL_NUMBER - 1 - i)*numbers[i];
            }
            
            return number;
        }
        
        @Override
        public int hashCode() {
            return number;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Configuration other = (Configuration) obj;
            return number == other.number;
        }

        @Override
        public String toString() {
            return "<" + stringify(number) + ">";
        }
    }
    
    static int pow(int num, int pow) {
        int res = 1;
        for (int i = 0; i < pow; i++) {
            res *= num; 
        }
        
        return res;
    }
}
